/**
 * 判断无向图是否为一棵树
 * 
 * 无向图G是一棵树的条件是：G必须是无环路的连通图或者由n-1条边的连通图。
 * 这里采用后者作为判断条件。
 * 对于联通的判定，可以用能否依次遍历全部顶点来实现。
 * 使用深度优先遍历在遍历图的过程中统计可能访问的定点数和边数
 * 若依次遍历就能访问到n个顶点和n-1条边，那么就是一棵树
 * 
 * 总结就是：1.用一遍遍历可以遍历完所有节点，保证连通性
 *          2. 用记录的边数和节点数，保证没有环
 */

#include"store_matrix.h"

void visit(int i){};//为了逻辑合理
bool isTree(MGraph *g){
    int visited[100];//访问标记数组初始化
    for(int i=1;i<g->vernum;i++){
        visited[i]=false;
    }
    int v_num=0,e_num=0;
    dfs(g,1,v_num,e_num,visited);//开始深度遍历
    //因为深度优先遍历对访问从开始节点开始，访问完所有可以访问的节点就退出了，所以如果没有联通，会导致有些节点在dfs之后visited仍然为0
    //符合要求，记录顶点和g拥有的节点数量相同，而且记录的边数和
    //为什么是e_num==2*(g->vernum-1)
    //是因为在无向图中每条边会在深度优先遍历中被访问两次，一次从一个顶点到另一个顶点，另一次从另一个顶点到第一个顶点。
    if(v_num==g->vernum&&e_num==2*(g->vernum-1))
        return true;
    else
        return false;

}

void dfs(MGraph* g,int v,int &v_num,int &e_num,int visited[]){
    visited[v]=true;//标记访问，然后给顶点计数
    v_num++;
    int w=firstNeighbor(g,v);//获取v的第一个邻接顶点
    while (w!=-1)//开始深度优先遍历
    {
        e_num++;//给边计数
        if(!visited[w])//第一个没有被访问的节点，递归进去（深度）
            dfs(g,w,v_num,e_num,visited);
        w=nextNeighbor(g,v,w);
    }
}
